#include <bits/stdc++.h>

using namespace std;
int e[210][210];

int main(){
    freopen("../A1150.txt","r",stdin);
    int N,M;
    cin>>N>>M;

    int a,b,c;
    while(M--){
        cin>>a>>b>>c;
        e[a][b] = e[b][a] = c;
    }

    int Q; int shortest = 99999999,cnt=-1;
    cin>>Q;
    for(int i=1;i<=Q;i++){
        int k;
        cin>>k;
        int distance = 0,flag1 = 1,start; //flag1:是否通路
        cin>>a; start = a;
        for(int j=0;j<k-1;j++){
            cin>>b;
            if(e[a][b]) distance += e[a][b];
            else flag1 = 0;
            a = b;
        }
        if(!flag1) {
            cout<<"Path "<<i<<": NA (Not a TS cycle)"<<endl;
            continue;
        }
        if(distance < shortest && k>=N+1){
            shortest = distance;
            cnt = i;
        }
        if(k==N+1 && start==b) cout<<"Path "<<i<<": "<<distance<<" (TS simple cycle)"<<endl;
        else if(k<N+1 || start!=b) cout<<"Path "<<i<<": "<<distance<<" (Not a TS cycle)"<<endl;
        else cout<<"Path "<<i<<": "<<distance<<" (TS cycle)"<<endl;
    }
    cout<<"Shortest Dist("<<cnt<<") = "<<shortest;
}